package com.example.demo.leetcode.top;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
 * 请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

 * 示例 1：
 *
 * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 * 示例 2：
 *
 * 输入：intervals = [[1,4],[4,5]]
 * 输出：[[1,5]]
 * 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-intervals
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 **/
public class Qujian_合并区间 {


    public int[][] merge2(int[][] intervals) {

        Arrays.sort(intervals,Comparator.comparingInt(v->v[0]));
        List<int []> res = new ArrayList<>();
        res.add(intervals[0]);

        for(int i=1;i<intervals.length;i++){
            //获取最左边
            int[] left = res.get(res.size() - 1);
            //获期最右边
            int[] right = intervals[i];
            //左边>右边,合并
            if(left[left.length-1]>=right[0]){
                left[left.length-1]=Math.max(right[right.length-1],left[left.length-1]);
            }else{
                //左边<右边,res重新塞入一个
                res.add(right);
            }
        }

        //res转换成二维数组
        int [][] end= new int[res.size()][2];
        int start=0;
        for(int[] temp:res){
            end[start][0]=temp[0];
            end[start][1]=temp[1];
            start++;
        }
        return end;
    }








    public int[][] merge(int[][] intervals) {

        //1.先将区间按照起点进行排序,从小到大
        Arrays.sort(intervals, Comparator.comparingInt(v->v[0]));

        List<int []> res = new ArrayList<>();
        //添加开头最小的区间,作为结果集
        res.add(intervals[0]);

        for(int i=1;i<intervals.length;i++){
            //拿到比较集合的最左边
            int[] interval = intervals[i];
            //拿到结果集合的最右边
            int[] end = res.get(res.size() - 1);

            //比较集合最左边> 结果集合最右边， 塞入res作为新的累加集合
            if(interval[0]>end[1]){
                res.add(interval);
            }else{
            //比较集合最左边 <= 结果集合最右边， 将结果集合的最右边和比较集合的最右边取最大值
                end[1]=Math.max(end[1],interval[1]);
            }
        }
        int[][] arr =new int[res.size()][2];
        int x=0;
        for(int[] temp :res){
            arr[x][0]=temp[0];
            arr[x][1]=temp[1];
            x++;
        }
        return arr;
    }

}
